/*
题目描述：两个链表的第一个公共结点
方法：
公共结点意味着value值相同，next指针相同，也就意味着两个链表在公共结点之后会合并成一条线
统计两个链表的长度len1, len2，长的链表先走abs(len2 - len1)
然后两个链表一起走，比较是否相等
 */
public class E52 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(3);
        node1.next.next.next = new ListNode(4);
        node1.next.next.next.next = new ListNode(5);

        ListNode node2 = new ListNode(9);
        node2.next = new ListNode(8);
        node2.next.next = node1.next.next.next;

        ListNode res = FindFirstCommonNode(node1, node2);

        System.out.println(res.value);
    }

    public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null){
            return null;
        }
        int len1 = len(pHead1);
        int len2 = len(pHead2);
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        if(len1 > len2){
            p1 = walk(p1, len1 - len2);
        }
        else{
            p2 = walk(p2, len2 - len1);
        }

        while(p1 != null && p2 != null){
            if(p1 == p2){
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;

    }

    public static int len(ListNode p){
        int count = 1;
        while(p!= null){
            p = p.next;
            count ++;
        }
        return count;
    }

    public static ListNode walk(ListNode p, int step){
        while(step != 0){
            p = p.next;
            step--;
        }
        return p;
    }
}
